COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00019 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a54.tex[154,phy] \today\hfill}

\parskip 5pt
\bigskip

\line{\bf Final Exam -- Part I. June 10, 1986 \hfill}
\medskip
\line{\bf True or False.\hfill}

\medskip
\disleft 40pt:\phantom{0}1. \hrulefill:
It is decidable whether a given Turing machine halts on all inputs.
FALSE.

\disleft 40pt:\phantom{0}2. \hrulefill:
The set of ambiguous CFGs is RE.
TRUE.

\disleft 40pt:\phantom{0}3. \hrulefill:
The intersection of two CFLs is accepted by some composition of two
pushdown transducers. TRUE.

\disleft 40pt:\phantom{0}4. \hrulefill:
Context-free languages are closed under set difference, $L↓1-L↓2$. FALSE.

\disleft 40pt:\phantom{0}5. \hrulefill:
Some 2-way (i.e., 2-way input, one stack) pushdown machines accept non-CFLs.
TRUE.

\disleft 40pt:\phantom{0}6. \hrulefill:
The image of $\Sigma↑{\ast}$ under a DPDM mapping is an unambiguous CFL.
FALSE.

\disleft 40pt:\phantom{0}7. \hrulefill:
If the input-output relation of a nondeterministic Turing machine is a
partial function, it is the I/O relation of some deterministic TM.
TRUE.

\disleft 40pt:\phantom{0}8. \hrulefill:
Whether a 2-counter machine halts on all inputs is decidable.
FALSE.

\disleft 40pt:\phantom{0}9. \hrulefill:
The set of computations of a TM is RE.
TRUE.

\disleft 40pt:10. \hrulefill:
The set of non-computations (relative to some fixed alphabet) of a TM is RE.
TRUE.

\disleft 40pt:11. \hrulefill:
The CFLs are closed under DPD mappings.
FALSE.

\disleft 40pt:12. \hrulefill:
If $f(i)$ is the $i↑{\rm th}$ prime, $f$ is Turing-computable.
TRUE.

\disleft 40pt:13. \hrulefill:
There is a language accepted by a non-deterministic one-counter machine,
but not by a DPDM.
TRUE.

\disleft 40pt:14. \hrulefill:
Standardizing a NPDM results in a machine that always halts.
FALSE.

\disleft 40pt:15. \hrulefill:
The intersection of two languages, each accepted by a deterministic 1-counter
machine, is a CFL.
FALSE.

\disleft 40pt:16. \hrulefill:
Deterministic and non-deterministic TMs accept the same languages.
TRUE.

\disleft 40pt:17. \hrulefill:
Deterministic and non-deterministic TMs have the same input-output relations.
FALSE.

\disleft 40pt:18. \hrulefill:
NPDMs accept and generate the same set of languages. I.e., the languages
accepted by NPDMs are the languages generated by DPDMs.
TRUE.

\disleft 40pt:19. \hrulefill:
The language $a↑ib↑{i+j}c↑j$ is a CFL.
TRUE.

\disleft 40pt:20. \hrulefill:
It is decidable whether a DPDM accepts the empty language.
TRUE.

\vfill\eject

\line{\bf Final Exam -- Part II. June 10, 1986\hfill}

\medskip
\disleft 20pt:1.:
Prove or disprove: If a DPDM is given an infinite sequence of the same
character as input and it never halts, then it eventually starts repeating
the same sequence of control states ($\in Q↑{\ast}$) forever.

\smallskip
\disleft 20pt::{\bf Solution.}
Standard undebugged proof: Since the machine runs forever, and there are
finitely many control states, it must repeat one, after which it will
necessarily go through the loop over and over.

\disleft 20pt::
This clearly proves too much; it doesn't mention that the memory is one
stack, so it purports to prove the result for Turing machines of all
kinds. But it is easy to find TMs that enter a certain state at longer and
longer intervals, so the state pattern doesn't repeat. Even one-stack
machines are not always in a loop {\sl yet\/} when they first repeat a state:

\bigskip
$$\vcenter{\halign{#\hfil\qquad
&#\hfil\qquad\qquad\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\qquad
&\hfil#\hfil\cr
{\tt START}&push 0&pop&1\cr
&push 1\cr
&push 1&0\cr
\noalign{\bigskip}
&&push 1&&pop&0\cr
\noalign{\bigskip}
&&&&1&Halt\cr}}$$

\bigskip
\display 20pt::
Non-standard, debugged proof: If the stack has a certain size infinitely
often, the machine must repeat an entire instantaneous description, after
which it repeats the intervening history forever. On the other hand, if it
has each size only finitely often, it eventually pushes characters that
are never popped, once for each size. The subsequent behavior depends
only on the character and the state, so when it happens twice with the
same character and state, the intervening history is repeated (except for
the permanently buried characters on the stack).

\vfill\eject

\figbox 3truein:

\display 40pt::
Pushdown machine; $+$ and $-$ are short for push and pop. How long does
it run? Generalize.

\medskip
\disleft 20pt:2.:
Define a {\sl shuffle\/} of $x$ and $y$ as any way of interspersing the
characters of $x$ and~$y$; if $x=x↓1x↓2\ldots x↓n$, $y=y↓1y↓2\ldots y↓n$,
$x↓i$~and $y↓i\in \Sigma↑{\ast}$, then
$x↓1y↓1x↓2y↓2\ldots x↓ny↓n$ is a shuffle of $x$ and~$y$.
The shuffles of $ab$ and $cd$ are
$$abcd\quad acbd\quad acdb\quad cabd\quad cadb\quad cdab\,.$$
If $L↓1$ and $L↓2$ are languages, the {\sl shuffle\/} of $L↓1$ and $L↓2$ is
$$\{\,z\mid z\hbox{ is a shuffle of $x\in L↓1$ and $y\in L↓2$}\,\}.$$

\display 40pt:(A):
Is the shuffle of $\{a↑ib↑i\}$ with $\{c↑jd↑j\}$ a CFL?

\display 40pt::{\bf Solution:}
The shuffle includes $a↑nc↑nb↑nd↑n$, where $n$ is from the pumping lemma,
and all characters have weight~1. No pumpable part can reach from the~$a$'s
to the~$b$'s, or from the~$c$'s to the $d$'s, so pumping gives a bad string.

\display 40pt:(B):
Is the shuffle of $\{a↑{\ast}\}$ with $\{\,a↑ib↑jc↑j\mid i≤j\,\}$
a CFL?

\display 40pt::{\bf Solution:}
The shuffle is just $\{b↑jc↑j\}$ padded with $a$'s, an obvious CFL.

\display 40pt:(C):
Is the shuffle of $\{a↑{\ast}d\}$ with $\{\,a↑ib↑jc↑j\mid i≤j\,\}$ a CFL?

\display 40pt::{\bf Solution:}
Intersect the shuffle with $da↑{\ast}b↑{\ast}c↑{\ast}$ to get the non-CFL
language $\{\,da↑ib↑jc↑j\mid$\break
$i≤j\,\}$, so the shuffle must not have been a CFL.

\vfill\eject

\disleft 20pt:3.:
Define a language $L$ of which the GSM images are exactly those languages
accepted by nondeterministic one-counter machines. Be careful: $L↓{(\,)}$,
the one-parenthesis language, is plausible but doesn't work.

\display 20pt::{\bf Solution:}
The language $L$ of possible action sequences of a counter is as good as any.
The actions are add~1, subtract~1, test zero, test nonzero. As on the takehome,
a~GSM maps~$L$ to the computations of any desired one-counter machine, and
a further GSM mapping gives the input strings those computations accept,
so all languages accepted by NCMs are GSM images of~$L$.

\display 20pt::
If language $L'=L\circ R↓M$ is a GSM image of~$L$, one shows that $y\in L'$
by finding a computation~$z$ of~$M$ that reads some $x\in L$ and
writes~$y$. A~NCM can guess and check the characters of~$z$, using its
counter to check that $x\in L$, and checking its input against~$y$. Thus
all GSM images of $L$ are languages accepted by NCMs.

\display 20pt::
$L$ itself is a GSM image of $L$, is accepted by a NCM, which is a PDM,
so $L$ is a CFL.

\disleft 20pt:4.:
Show that it is undecidable whether the language of a CFG contains any
palindromes.

\display 20pt::{\bf Solution:}
Convert the question whether CFLs  $L↓1$ and $L↓2$ intersect, into the
question whether the CFL $L↓1 : \hat{L}↓2$ includes any palindromes, where
`:' is a character not used in $L↓1\cup L↓2$. If we could decide the
presence of palindromes, we could decide intersection problems for CFLs,
a~known undecidable problem.

\display 20pt::
The standard undebugged proof for this problem converts the question whether
CFL~$L$ contains a palindrome into the question whether $L$ intersects the
obvious CFL of palindromes. The fallacy is that there might be an algorithm
for that subset of intersection problems, even though there is none for the
full set of intersection problems. For example, intersection problems where
one language is finite are easy.

\disleft 20pt:5.:
Let $R$ be the input-output relation of a nondeterministic TM with one-character
input and output alphabet, say $\{1\}$. Define $R↓{\rm min}$ as the partial
function mapping each input accepted by the NTM into the shortest associated
output; $\{\,\langle x,y\rangle\mid y\hbox{ is the shortest for which
$xRy$}\,\}$.

\disleft 20pt::
Prove or disprove that $R↓{\rm min}$ must be the input-output relation of a
deterministic Turing machine.

\display 20pt::{\bf Solution:}
Let $R$, on input $\langle d,x\rangle$, output 11, or (using the
non-determinism), search for a computation of the machine described by~$d$
that reads~$x$, and if that search halts, output~1. Then $R↓{\rm min}$
maps halting pairs into~1, non-halting pairs into~11. If we could
implement $R↓{\rm min}$ on a Turing machine, we could decide halting
problems, absurd. Of course there are other relations~$R$ for which
$R↓{\rm min}$ is computable.

\vfill\eject

\disleft 20pt:6.:
The lectures defined the language {\sl generated\/} by a NTM as the set of
outputs of computations. Hopcroft and Ullman, on pg.~168, define the
language {\sl generated\/} by a deterministic TM as those $x↓i$ that appear,
terminated by \#, in the output sequence
$$x↓1\#\, x↓2\#\,\ldots\,x↓i\#\,\ldots\;,$$
possibly infinite, written by a ``computation'' of the machine that may go
on forever. Show that a language generated in either sense is generated
in the other sense. Proofs in ordinary English are acceptable and preferred
to pages of detailed Turing machine programs, which will be full of bugs
anyway.

\display 20pt::{\bf Solution:}
Suppose $L$ is generated by a NTM. Use the universal machine method
to find all computations of the NTM, and for each, print its output followed
by~\#. This generates the language in the Hopcroft-Ullman way.

\display 20pt::
Conversely, suppose $L'$ is generated by a DTM in the H\&U way. Modify
the machine so that it outputs only one of the $x↓i$'s, and accepts
instead of writing the~\# at the end. (Use of nondeterminism and one bit 
stored in the control state does the trick.)


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
June 23, 1986.
%revised date;
%subsequently revised.

\bye